package leetCode.solution;

import java.util.HashMap;

import com.alibaba.fastjson.JSON;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

 * @author jerry
 * @ClassName:  Solution560   
 * @Description:TODO(描述这个类的作用)   
 * @date 2022年11月22日 下午3:25:51
 */
public class Solution560 {
	
	public static void main(String[] args) {
		int maxSize = 20;
		int maxValue = 100;
		int maxK = 1000;
		for(int i=0;i<500000;i++) {
			int size = (int)(Math.random()*maxSize);
			int k = (int)(Math.random()*maxK);
			int [] arr = new int[size];
			for(int j=0;j<size;j++) {
				arr[j]=(int)(Math.random()*maxValue);
			}
			int result = new Solution560().subarraySum(arr, k);
			int result1 = new Solution560().subarraySum1(arr, k);
			int result2 = new Solution560().subarraySum2(arr, k);
			if(result!=result1 || result!=result2) {
				System.out.println("Oops!");
				System.out.println(k);
				System.out.println(JSON.toJSONString(arr));
				System.out.println(result + " " +result1+ " " +result2);
			}
		}
	}
	
	public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        for (int left = 0; left < len; left++) {
            int sum = 0;
            // 区间里可能会有一些互相抵销的元素
            for (int right = left; right < len; right++) {
                sum += nums[right];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }


	public int subarraySum1(int[] nums, int k) {
		if(nums==null|| nums.length<1) return 0;
		int n = nums.length;
		int count= 0;
		for(int i = 0;i<n;i++) {
			int sum = 0;
			for(int j = i;j<n;j++) {
				sum+=nums[j];
				if(sum==k) {
					count++;
				}
			}
		}
		return count;
    }
	
	public int subarraySum2(int[] nums, int k) {
		int count = 0, pre = 0;
		HashMap<Integer, Integer> map = new HashMap<>();
		map.put(0, 1);
		for (int i = 0; i < nums.length; i++) {
			pre += nums[i];
			if (map.containsKey(pre - k)) {
				count += map.get(pre - k);
			}
			map.put(pre, map.getOrDefault(pre, 0) + 1);
		}
		return count;
	}
}
